\documentclass{ctexart}

\usepackage{graphicx}
\usepackage{amsmath}

\title{堆排序和快速排序的比较和测试}


\author{胡宇梦 \\ 信息与计算科学　3210103435}


\begin{document}

\maketitle

\section{堆排序和快速排序测试}
将数组大小从100000增加到600000，输入数组的有序度分别设为1\%、10\%、90\%、99\%。
其中设置数组有序度的代码如下：
\begin{verbatim}
///传入数组容器和有序度rate
vector<Comparable> RandomVector(std::vector<Comparable>& _arr,double rate)   
{
    std::vector<Comparable> new_arr;        ///生成新数组
    int i;
    int n = _arr.size();
    for (i = _arr.size()*rate; i > 0; i--)  ///弄乱数组前_arr.size()*rate个数
    {
        srand(unsigned(time(NULL)));
        /// index记录选中的随机下标
        int index = rand() % i;
        /// 将选中下标对应的元素push到新数组
        new_arr.push_back(_arr[index]);
        /// 将原数组中选中的元素剔除
        _arr.erase(_arr.begin() + index);
    }
    for (i = n* rate; i < n;i++)           ///设置数组中的有序列
    {
         new_arr.push_back(i);
    }
    return new_arr;  /// 返回新数组
}
\end{verbatim}

测试时，对于每个n，依次测试四组有序度，以防偶然性，每组数据测试三次，测试主要函数如下：

\begin{figure}[ht]
    \centering
    \includegraphics[width=13cm]{2.png}
    \caption{test()函数}
    \label{mode=2}
\end{figure}  

测试结果如下图所示：


\begin{figure}[ht]
    \centering
    \includegraphics[width=13cm]{效率图.jpg}
    \caption{两种排序算法的效率对比图}
    \label{mode=1}
\end{figure}  




\section{测试结果分析}

2.1  如测试可见，在10w以上的数据量上，n不变，快速排序消耗的时间明显小
于堆排序，即快速排序的速度明显优于堆排序，且随着数据量的增加快速排序
效率要高的多。

分析：快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排
序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于
等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排
序一样每次只能在相邻的数之间进行交换，交换的距离就
大的多了。因此总的比较和交换次数就少了，速度自然就提高了。

\dots

2.2  如测试可见，当n不变，当输入数据越有序，堆排序和快速排序的效率越低。

分析：对于快速排序而言，在最坏的情况下，比如原本就有序的数列，或者有
大量元素相等的数列，可能是相邻的两个数进行了交换。因此快速排序的最差
时间复杂度和冒泡排序是一样的都是O（n²），而它的平均时间复杂度
为O(nlogn)，所以n不变，输入数组越有序，效率越低。

对于堆排序而言，堆排序排序的第一步是建堆，建堆过程会打乱
数据原有的相对先后顺序，导致数据的有序度降低。比如，对于一组
已经有序的数据来说，经过建堆之后，
数据反而变得更无序了。相应的，效率也会更低

\dots

2.3  快速排序的基本思想是：通过一趟排序将要排序的数据分割成独立的两部
分，其中一部分的所有数据比另一部分的所有数据要小，再按这种方法对这两
部分数据分别进行快速排序，整个排序过程可以递归进行，使整个数据变成有
序序列。

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点
的键值或索引总是小于（或者大于）它的父节点。利用大顶堆(小顶堆)堆
顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大
记录(最小记录)变得简单

实际应用中，堆排序的时间复杂度要比快速排序稳定，快速排序的最差
的时间复杂度是O（n²）,平均时间复杂度是O(nlogn)。堆排序的时间
复杂度稳定在O(nlogn)。但是从综合性能来看，快速排序性能更好
\begin{figure}[ht]
    \centering
    \includegraphics[width=13cm]{1.jpg}
    \caption{两种排序算法的时间复杂度}
    \label{mode=3}
\end{figure}  


\section{Quicksort算法改进（三路快排）}
书本上对于原始的Quicksort的改进办法有：

（1） 三数中值分割法。即用左端、右端和中心位置上的三个元素的中值作为枢
纽元，消除了预排序输入的坏情形

（2） 结合直接插入排序。此改进办法主要针对小数组，对于很小的数组（N<20）,快速排序不如插入排序好，不仅如此，因为快速排序是递归的，这种情形经常发生，对于小数组使用插入排序法，可以提高效率。

当输入数组区间的相等元素较多的时候，相等元素本不应交换，原始的Quicksort交换
相等的元素，增加了不应有的开销，这样导致算法最后可能退化成O（n²）的算法，所以本项目针对相等元素较多的数组对Quicksort进行改进，采用三路快排。

三路快排：
\begin{figure}[ht]
    \centering
    \includegraphics[width=15cm]{3.png}
\end{figure}  

代码以及注释如下：
\begin{verbatim}
    /********************三路快速排序算法实现*****************/
    template<typename Comparable>
    void __quickSort3Ways(Comparable a[], int left, int right)
    {
        /* 对递归到数据量较小时使用插入排序 */
        if (right - left <= 40) {                 
            insertionSort<Comparable>(a, left, right);
            return;
        }
    
        const Comparable & v = median3(a, left, right);
        // 将<v的分界线的索引值lt初始化为第一个元素的位置
        （也就是<v部分的最后一个元素所在位置）
        int lt = left;       
        // 将>v的分界线的索引值gt初始化为最后一个元素right的后一
        个元素所在位置（也就是>v部分的第一个元素所在位置）
        int gt = right + 1;  
        int i = left + 1;    // 将遍历序列的索引值i初始化为 left+1
    
        while (i < gt) {     // 循环继续的条件
            if (a[i] < v) {
                // 如果当前位置元素<v，则将当前位置元素与=v部分的第
                一个元素交换位置
                std::swap(a[i], a[lt + 1]);  
                i++;                             // i++  考虑下一个元素
                lt++;                            // lt++  表示<v部分多了一个元素
            }
            // 如果当前位置元素>v，则将当前位置元素与>v部分
            的第一个元素的前一个元素交换位置
            else if (a[i] > v) {               
                // 此时i不用动，因为交换过来的元素还没有考虑他的大小
                std::swap(a[i], a[gt - 1]);  
                gt--;                            // gt--  表示>v部分多了一个元素
            }
            //  如果当前位置元素=v   则只需要将i++即可，表示=v部分多了一个元素
            else {             
                i++;
            }
        }
        // 上面的遍历完成之后，将整个序列的第一
        个元素(也就是"基准"元素)放置到合适的位置
        std::swap(a[left], a[lt]);   
        // 也就是将它放置在=v部分即可
        // 对<v部分递归调用__quickSort3Ways函数进行三路排序
        __quickSort3Ways<Comparable>(a, left, lt - 1); 
        // 对>v部分递归调用__quickSort3Ways函数进行三路排序
        __quickSort3Ways<Comparable>(a, gt, right);    
    }
    
    template<typename Comparable>
    void quickSort3Ways(Comparable a[], int count)
    {
        std::srand(std::time(NULL));               /* 种下随机种子 */
        /* 调用__quickSort3Ways函数进行三路快速排序 */
        __quickSort3Ways<Comparable>(a, 0, count - 1);   
    }
\end{verbatim}

将n固定为10000，测试一般随机数组和大量元素重复序列在快速排序和改进的
测试结果如下：
\begin{figure}[ht]
    \centering
    \includegraphics[width=8cm]{4.jpg}
\end{figure}  

\begin{figure}[ht]
    \centering
    \includegraphics[width=8cm]{5.jpg}
\end{figure}  
总结：改进的三路快排算法大体基于快速排序算法，针对一般的序列，效率低于快速排序算法，
针对大量重复元素的序列，改进的三路快排算法明显优于快速排序算法。
\end{document}
